import java.util.*;
/*
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', 
determine if the input string is valid.

The brackets must close in the correct order, 
"()" and "()[]{}" are all valid but "(]" and "([)]" are not.
"({[]})"
=> true
*/
public class Solution{
	public boolean isValid(String s) {
		if(s==null || "".equals(s))
			return true;
		int len = s.length();
		if(len%2 != 0)
			return false;
		HashMap<String,String> map = new HashMap<String,String>();
		map.put("(",")");
		map.put("[","]");
		map.put("{","}");
		Stack<String> stack = new Stack<String>();
		String ch;
		for(int i=0; i<s.length(); i++){
			ch = s.charAt(i) + "";
			if(map.keySet().contains(ch)){
				stack.push(ch);
			}else if(map.values().contains(ch)){
				if(!stack.empty()&&ch.equals(map.get(stack.peek()))){
					stack.pop();
				}else{
					return false;
				}
			}
		}
		return stack.empty();
	}
	public static void main(String[] args){
		Solution solution = new Solution();
		String s = "({)}";
		if(args.length!=0)
			s = args[1];
		boolean res = solution.isValid(s);
		System.out.println(res);
	}
}